I modelli lineari visti finora condividono un’architettura comune: si sceglie a priori un insieme di funzioni base, si proiettano gli input nel feature space corrispondente e si apprende un modello lineare in quello spazio. Questa architettura ha due limiti strutturali: le basi sono fisse e non si adattano ai dati, e il loro numero esplode con la dimensionalità dell’input (la maledizione della dimensionalità). I metodi kernel aggirano entrambi i limiti con un cambio di prospettiva radicale: invece di descrivere ogni punto con le sue coordinate in un feature space costruito esplicitamente, descrivono il dataset tramite le similarità tra coppie di punti, calcolate da una funzione kernel. Il feature space continua a esistere, ma resta implicito: può essere enorme, persino a dimensione infinita, senza che nessuno debba mai calcolarlo. Il capitolo sviluppa questa idea in quattro tappe: la riscrittura della ridge regression in forma duale (dove compaiono solo i kernel), la teoria dei kernel validi e le regole per costruirne di nuovi, la regressione kernel non parametrica, e infine i processi gaussiani, che estendono la regressione bayesiana dal mondo dei pesi al mondo delle funzioni. Chiudono il capitolo due esercizi d’esame svolti passo per passo.

Riferimenti sul testo: Bishop, Pattern Recognition and Machine Learning [PRML], capitolo 6 (6.1, 6.2, 6.3, 6.4) e sezione 2.5.1.

1. Dalle feature esplicite alle similarità#

1.1 Il limite dei modelli lineari a basi fisse#

Molti problemi reali presentano pattern non lineari: nella regressione la relazione input-output può non essere lineare, nella classificazione le classi possono non essere separabili da un confine lineare. I modelli lineari puri non sono abbastanza ricchi per catturarli. La soluzione già incontrata è il feature mapping: una trasformazione $\Phi: \mathbf{x} \to \boldsymbol{\phi}(\mathbf{x})$ che porta i dati in uno spazio a dimensionalità più alta, dove i pattern diventano lineari e i metodi lineari tornano a funzionare.

Due esempi rendono concreta l’idea:

• Classificazione binaria in 1D: punti di due classi disposti sull’asse reale in modo che nessuna soglia li separi (per esempio una classe al centro e l’altra ai due estremi). Mappando l’input scalare nel feature space bidimensionale $x \to \{x, x^2\}$, i punti diventano separabili da una retta: la parabola $x^2$ “solleva” i punti lontani dall’origine e li allontana da quelli centrali.
• Classificazione binaria in 2D: una classe dentro un anello e l’altra fuori, nessuna retta separa le due nel piano $\mathbf{x} = \{x_1, x_2\}$. Con la mappa $\mathbf{x} = \{x_1, x_2\} \to \mathbf{z} = \{x_1^2, \sqrt{2}\, x_1 x_2, x_2^2\}$ i punti diventano separabili da un piano nel nuovo spazio tridimensionale.

Il problema è il costo di questa strategia. Si consideri un mapping quadratico completo per un problema con $M$ variabili di input: servono il termine costante, gli $M$ termini lineari, gli $M$ quadrati e tutti i prodotti incrociati $x_i x_j$, per un totale che cresce come $O(M^2)$. Con un mapping di grado $d$ il numero di feature cresce come $O(M^d)$. È la maledizione della dimensionalità già incontrata: il numero di feature cresce così in fretta con il numero di variabili che il calcolo esplicito del mapping diventa rapidamente infattibile.

I metodi kernel affrontano esattamente questo problema: non richiedono di calcolare esplicitamente il feature mapping. Restano metodi computazionalmente costosi, ma fattibili anche quando il feature space è enorme o infinito. Dal punto di vista del compromesso bias-varianza, il loro scopo è ridurre il bias del modello, cioè aumentarne la complessità, dando accesso a feature space molto più ricchi di quelli costruibili a mano.

1.2 Modelli parametrici e metodi memory-based#

I metodi kernel appartengono a una famiglia diversa da quella dei modelli visti finora, e la distinzione merita di essere esplicitata.

La regressione lineare è il prototipo del metodo parametrico: appresi i pesi $\mathbf{w}$, i dati non servono più. I metodi memory-based, come il k-nearest neighbour, sono all’estremo opposto: l’addestramento è tipicamente rapidissimo (spesso si limita a memorizzare i dati), ma la predizione è lenta perché richiede di confrontare il nuovo punto con i campioni memorizzati. I metodi kernel e i processi gaussiani vivono in questo secondo mondo: la predizione per un nuovo punto è costruita direttamente a partire dalle similarità con i punti del training set.

In parole semplici: un metodo parametrico studia i dati, ne distilla poche cifre (i parametri) e butta via i dati. Un metodo memory-based tiene tutti i dati in memoria e, davanti a un nuovo caso, risponde guardando i casi vecchi più simili. I metodi kernel funzionano nel secondo modo.

1.3 L’idea: la similarità al posto delle coordinate#

Idea chiave: ogni feature mapping $\boldsymbol{\phi}$ induce una nozione di similarità tra punti, il prodotto scalare $\boldsymbol{\phi}(\mathbf{x})^T\boldsymbol{\phi}(\mathbf{x}')$. I metodi kernel riscrivono gli algoritmi lineari in modo che compaiano solo queste similarità, mai le coordinate $\boldsymbol{\phi}(\mathbf{x})$: a quel punto basta saper calcolare la similarità, e il feature space può restare implicito, arbitrariamente grande, perfino infinito.

Il vantaggio è duplice. Primo, computazionale: spesso la similarità si calcola con poche operazioni anche quando il feature space corrispondente ha dimensione enorme. Secondo, concettuale: definire una similarità sensata tra due oggetti è in generale più facile che progettare un buon insieme di coordinate, soprattutto per dati non vettoriali come grafi, insiemi, stringhe o testi.

2. La funzione kernel#

2.1 Definizione e interpretazione#

Dalla definizione discendono subito tre proprietà e osservazioni:

• il kernel è simmetrico: $k(\mathbf{x}, \mathbf{x}') = k(\mathbf{x}', \mathbf{x})$, perché il prodotto scalare lo è;
• il kernel si interpreta come una misura di similarità tra $\mathbf{x}$ e $\mathbf{x}'$: il prodotto scalare è grande quando i due vettori di feature puntano nella stessa direzione e hanno norma grande, piccolo o nullo quando sono ortogonali;
• vettori di feature molto grandi, persino a dimensione infinita, possono dare luogo a una funzione kernel facile da calcolare: questa è la molla dell’intero approccio.

Ogni insieme finito di funzioni base induce il proprio kernel: date le basi $\phi_1, \dots, \phi_M$ (polinomiali, gaussiane, sigmoidali…), il kernel corrispondente è $k(x, x') = \sum_i \phi_i(x)\phi_i(x')$. Fissato $x'$, la funzione $k(x, x')$ vista come funzione di $x$ ha la forma tipica di una “campana” di similarità centrata attorno a $x'$, con profilo che dipende dalla famiglia di basi scelta.

Due classi speciali di kernel hanno un nome proprio:

• kernel stazionari: dipendono solo dalla differenza tra gli argomenti, $k(\mathbf{x}, \mathbf{x}') = k(\mathbf{x} - \mathbf{x}')$; la similarità è invariante per traslazione;
• kernel omogenei (o radial basis functions, RBF): dipendono solo dalla distanza, $k(\mathbf{x}, \mathbf{x}') = k(\lVert \mathbf{x} - \mathbf{x}' \rVert)$.

In parole semplici: un kernel è un termometro di somiglianza: prende due punti e restituisce un numero che dice quanto si assomigliano, dove “assomigliarsi” significa avere feature simili in un certo spazio. Il colpo di genio è che spesso si può calcolare quel numero senza mai costruire le feature.

2.2 Il kernel trick#

A che cosa serve, operativamente, la funzione kernel? È possibile rielaborare la rappresentazione dei modelli lineari in modo da sostituire tutti i termini che coinvolgono $\boldsymbol{\phi}(\mathbf{x})$ con termini che coinvolgono soltanto $k(\mathbf{x}, \cdot)$. In altre parole, l’output di un modello lineare può essere calcolato usando solo le similarità tra campioni.

Idea chiave (kernel trick): se un algoritmo lineare può essere riscritto in modo che gli input compaiano esclusivamente dentro prodotti scalari $\boldsymbol{\phi}(\mathbf{x})^T\boldsymbol{\phi}(\mathbf{x}')$, allora ogni prodotto scalare può essere sostituito da un kernel $k(\mathbf{x}, \mathbf{x}')$: l’algoritmo lavora così, implicitamente, nel feature space associato al kernel, senza mai calcolarlo.

Questo approccio, chiamato appunto kernel trick, si applica a molti algoritmi di apprendimento: la ridge regression, la regressione k-NN, il perceptron, la PCA non lineare, i processi gaussiani, le Support Vector Machines (oggetto del prossimo capitolo) e altri ancora.

In parole semplici: molti algoritmi, guardati bene, usano i dati solo per farne prodotti scalari a coppie. Se è così, si può staccare l’algoritmo dalle coordinate e attaccarlo a una funzione di similarità qualsiasi: l’algoritmo non se ne accorge, ma di fatto sta lavorando in uno spazio nuovo, anche gigantesco, al prezzo di calcolare qualche similarità.

3. Kernel ridge regression: la rappresentazione duale#

Il primo esempio completo di kernel trick è la riscrittura della ridge regression. È il passaggio tecnico centrale del capitolo, perché mostra concretamente come le feature esplicite spariscano dai conti.

3.1 Dal primale al duale#

Si parte dalla funzione di perdita della ridge regression (capitolo 3):

$$L(\mathbf{w}) = \frac{1}{2} \sum_{n=1}^{N} \big( \mathbf{w}^T \boldsymbol{\phi}(\mathbf{x}_n) - t_n \big)^2 + \frac{\lambda}{2}\, \mathbf{w}^T \mathbf{w}$$

Per risolverla si annulla il gradiente rispetto a $\mathbf{w}$:

$$\nabla_{\mathbf{w}} L = \sum_{n=1}^{N} \big( \mathbf{w}^T \boldsymbol{\phi}(\mathbf{x}_n) - t_n \big)\, \boldsymbol{\phi}(\mathbf{x}_n) + \lambda \mathbf{w} = 0$$

Invece di risolvere direttamente per $\mathbf{w}$, si osserva che dall’equazione si può isolare $\mathbf{w}$ come combinazione lineare dei vettori di feature dei campioni:

$$\mathbf{w} = -\frac{1}{\lambda} \sum_{n=1}^{N} \big( \mathbf{w}^T \boldsymbol{\phi}(\mathbf{x}_n) - t_n \big)\, \boldsymbol{\phi}(\mathbf{x}_n) = \sum_{n=1}^{N} a_n\, \boldsymbol{\phi}(\mathbf{x}_n) = \boldsymbol{\Phi}^T \mathbf{a}$$

dove si è introdotto il cambio di variabile

$$a_n = -\frac{1}{\lambda} \big( \mathbf{w}^T \boldsymbol{\phi}(\mathbf{x}_n) - t_n \big)$$

e $\boldsymbol{\Phi}$ è la solita matrice di design $N \times M$. Il messaggio geometrico è già importante di per sé: il vettore dei pesi ottimo giace nel sottospazio generato dai vettori di feature dei campioni di training, quindi al posto degli $M$ pesi si possono usare come incognite gli $N$ coefficienti $a_n$, uno per campione. Questa è la rappresentazione duale: le variabili duali $\mathbf{a}$ vivono nello spazio dei campioni, non nello spazio dei parametri.

Sostituendo $\mathbf{w} = \boldsymbol{\Phi}^T \mathbf{a}$ nella perdita si ottiene una funzione delle sole variabili duali:

$$L(\mathbf{a}) = \frac{1}{2}\, \mathbf{a}^T \boldsymbol{\Phi}\boldsymbol{\Phi}^T \boldsymbol{\Phi}\boldsymbol{\Phi}^T \mathbf{a} \;-\; \mathbf{a}^T \boldsymbol{\Phi}\boldsymbol{\Phi}^T \mathbf{t} \;+\; \frac{1}{2}\, \mathbf{t}^T \mathbf{t} \;+\; \frac{\lambda}{2}\, \mathbf{a}^T \boldsymbol{\Phi}\boldsymbol{\Phi}^T \mathbf{a}$$

Le feature compaiono ormai soltanto attraverso il prodotto $\boldsymbol{\Phi}\boldsymbol{\Phi}^T$: è qui che entra in scena la matrice di Gram.

3.2 La matrice di Gram#

La matrice di Gram rappresenta le similarità tra ogni coppia di campioni del training set: sulla diagonale ci sono le similarità di ogni punto con sé stesso, fuori diagonale quelle tra punti diversi. È simmetrica per la simmetria del kernel. Attenzione a non confonderla con $\boldsymbol{\Phi}^T\boldsymbol{\Phi}$, che è $M \times M$ e vive nello spazio delle feature: $\mathbf{K} = \boldsymbol{\Phi}\boldsymbol{\Phi}^T$ è $N \times N$ e vive nello spazio dei campioni.

Riscritta con la matrice di Gram, la perdita duale diventa

$$L(\mathbf{a}) = \frac{1}{2}\, \mathbf{a}^T \mathbf{K}\mathbf{K}\, \mathbf{a} - \mathbf{a}^T \mathbf{K}\, \mathbf{t} + \frac{1}{2}\, \mathbf{t}^T \mathbf{t} + \frac{\lambda}{2}\, \mathbf{a}^T \mathbf{K}\, \mathbf{a}$$

Annullando il gradiente rispetto ad $\mathbf{a}$ si ottiene la soluzione in forma chiusa:

$$\mathbf{a} = (\mathbf{K} + \lambda \mathbf{I}_N)^{-1}\, \mathbf{t}$$

Nella soluzione duale le feature non compaiono più: bastano le similarità raccolte in $\mathbf{K}$ e i target.

In parole semplici: invece di chiedersi “quanto pesa ciascuna feature?” (un numero per feature, $M$ incognite), la forma duale si chiede “quanto conta ciascun esempio?” (un numero per esempio, $N$ incognite). Per rispondere non servono le coordinate degli esempi: basta la tabella delle somiglianze a coppie, cioè la matrice di Gram.

3.3 La funzione di predizione#

Come si calcola la predizione per un nuovo punto $\mathbf{x}$ usando la rappresentazione duale? Sostituendo $\mathbf{w} = \boldsymbol{\Phi}^T\mathbf{a}$ nel modello lineare:

$$y(\mathbf{x}) = \mathbf{w}^T \boldsymbol{\phi}(\mathbf{x}) = \mathbf{a}^T \boldsymbol{\Phi}\, \boldsymbol{\phi}(\mathbf{x}) = \sum_{n=1}^{N} a_n\, \boldsymbol{\phi}(\mathbf{x}_n)^T \boldsymbol{\phi}(\mathbf{x}) = \mathbf{k}(\mathbf{x})^T (\mathbf{K} + \lambda \mathbf{I}_N)^{-1}\, \mathbf{t}$$

dove $\mathbf{k}(\mathbf{x})$ è il vettore delle similarità tra il nuovo punto e tutti i punti del training set, con componenti $k_n(\mathbf{x}) = k(\mathbf{x}_n, \mathbf{x})$ per ogni $\mathbf{x}_n \in \mathcal{D}$.

La lettura della formula è illuminante: la predizione è una combinazione lineare dei target dei campioni di training, con coefficienti che dipendono dalle similarità tra il nuovo punto e i campioni stessi. Se il nuovo punto assomiglia molto a certi esempi, i target di quegli esempi pesano molto nella predizione. Anche il feature mapping esplicito è sparito dalla predizione: servono solo valutazioni del kernel.

In parole semplici: per predire il valore di un punto nuovo, il modello guarda i punti di training, misura quanto ciascuno somiglia al nuovo arrivato e fa una media pesata dei loro target, con pesi aggiustati dalla matrice $(\mathbf{K} + \lambda\mathbf{I})^{-1}$. È il funzionamento tipico di un metodo memory-based: la risposta viene dai vicini, non da parametri memorizzati.

3.4 Rappresentazione originale o duale?#

Le due rappresentazioni risolvono lo stesso problema, ma con costi e possibilità diverse.

• Rappresentazione originale (primale): richiede di invertire $(\boldsymbol{\Phi}^T\boldsymbol{\Phi} + \lambda\mathbf{I}_M)$, una matrice $M \times M$. È computazionalmente conveniente quando $M$ è piccolo, cioè quando il feature space è a bassa dimensionalità.
• Rappresentazione duale: richiede di invertire $(\mathbf{K} + \lambda\mathbf{I}_N)$, una matrice $N \times N$. Poiché tipicamente $N \gg M$, in apparenza è un pessimo affare; diventa conveniente quando $M$ è molto grande o addirittura infinito. Inoltre non richiede mai di calcolare esplicitamente $\boldsymbol{\Phi}$, il che rende l’approccio applicabile anche a tipi di dato complessi (grafi, insiemi, stringhe, testi) dove un vettore di feature non è nemmeno definito in modo naturale. Infine, la similarità tra campioni è in generale sia meno costosa da calcolare sia più facile da progettare rispetto al feature mapping completo.

In parole semplici: il primale paga il conto in base a quante feature ci sono, il duale in base a quanti dati ci sono. Con poche feature vince il primale; con feature infinite (o con dati che non stanno in un vettore, come un grafo o una frase) il primale è proprio impossibile, e il duale è l’unica strada.

4. Quali funzioni sono kernel validi#

4.1 Dalla similarità al feature space: il teorema di Mercer#

Finora il kernel è stato costruito a partire da un feature mapping dato. Ma il vero potenziale del metodo sta nel percorso inverso: progettare direttamente la funzione di similarità, senza passare dal feature space. A quel punto serve una garanzia: che la funzione scelta corrisponda davvero a un prodotto scalare in qualche feature space, altrimenti tutta la matematica della sezione precedente (in particolare l’invertibilità e la coerenza delle formule) crolla. Una funzione con questa garanzia si dice kernel valido.

In sintesi, le condizioni da verificare per un kernel valido sono:

1. continuità in entrambi gli argomenti;
2. simmetria: $k(\mathbf{x}, \mathbf{x}') = k(\mathbf{x}', \mathbf{x})$ per ogni coppia;
3. semidefinitezza positiva: per ogni numero di punti e per ogni loro scelta, la matrice di Gram costruita con $k$ è semidefinita positiva.

Se le condizioni valgono, esiste un feature mapping (che in generale non si conosce, e che può essere a dimensione infinita) tale che $k(\mathbf{x}, \mathbf{x}') = \boldsymbol{\phi}(\mathbf{x})^T\boldsymbol{\phi}(\mathbf{x}')$.

In parole semplici: non ogni funzione di due punti è una similarità legittima. Il test di legittimità è: comunque si scelgano dei punti, la tabella delle loro similarità reciproche deve essere una matrice semidefinita positiva (come lo è ogni matrice di covarianza). Se il test passa sempre, da qualche parte esiste uno spazio in cui quella funzione è un onesto prodotto scalare, anche se nessuno sa com’è fatto.

4.2 Come si verifica in pratica#

Verificare la condizione di Mercer direttamente, per ogni $N$ e ogni scelta di punti, è in generale impraticabile. Le strategie operative, tutte spendibili all’esame, sono quattro:

1. Esibire un feature mapping: se si riesce a scrivere $k(\mathbf{x}, \mathbf{x}') = \boldsymbol{\phi}(\mathbf{x})^T\boldsymbol{\phi}(\mathbf{x}')$ per un qualche $\boldsymbol{\phi}$ esplicito, la validità è dimostrata per definizione.
2. Usare le regole di combinazione (sezione 5.2): partire da kernel noti e applicare trasformazioni che preservano la validità.
3. Controllare la simmetria: se $k(\mathbf{x}, \mathbf{x}') \neq k(\mathbf{x}', \mathbf{x})$ anche per una sola coppia, la funzione non è un kernel; è il test più rapido per scartare un candidato.
4. Cercare un controesempio alla semidefinitezza: basta trovare una scelta finita di punti la cui matrice di Gram abbia un autovalore negativo (per esempio un elemento diagonale $k(\mathbf{x}, \mathbf{x}) < 0$, oppure una matrice $2 \times 2$ con determinante negativo) per concludere che il kernel non è valido.

Un avvertimento importante, che tornerà negli esercizi: valutare il candidato kernel su qualche coppia di punti e ottenere valori “ragionevoli” non dimostra nulla in positivo; le valutazioni puntuali servono solo a cercare controesempi.

5. Costruire kernel#

Non è necessario (né desiderabile) partire dal feature space per costruire un kernel: l’obiettivo è proprio evitare di calcolare esplicitamente i vettori di feature. Le due alternative principali sono la progettazione diretta da zero (verificando poi la validità) e la costruzione a partire da kernel esistenti tramite regole che preservano la validità.

5.1 Progettazione diretta: il kernel polinomiale#

Si consideri la funzione $k(\mathbf{x}, \mathbf{x}') = (\mathbf{x}^T\mathbf{x}')^2$. È un kernel valido? Si può verificarlo esplicitamente in uno spazio di input bidimensionale, espandendo il quadrato:

$$(\mathbf{x}^T\mathbf{x}')^2 = (x_1 x_1' + x_2 x_2')^2 = x_1^2 x_1'^2 + 2\, x_1 x_1' x_2 x_2' + x_2^2 x_2'^2 = \boldsymbol{\phi}(\mathbf{x})^T \boldsymbol{\phi}(\mathbf{x}')$$

con il feature mapping

$$\boldsymbol{\phi}(\mathbf{x}) = \big( x_1^2,\; \sqrt{2}\, x_1 x_2,\; x_2^2 \big)^T$$

La funzione corrisponde quindi al prodotto scalare in un feature space contenente solo i termini di secondo grado: è un kernel valido. Si noti anche il vantaggio computazionale: calcolare il kernel costa un prodotto scalare in dimensione 2 più un quadrato, mentre costruire esplicitamente le feature e poi moltiplicarle costerebbe di più, e il divario cresce con la dimensione dell’input e con il grado.

Due estensioni immediate:

• per ottenere anche i termini costanti e lineari si definisce $k(\mathbf{x}, \mathbf{x}') = (\mathbf{x}^T\mathbf{x}' + c)^2$ con $c > 0$;
• per ottenere tutti i termini fino al grado $z$ si definisce il kernel polinomiale generale $k(\mathbf{x}, \mathbf{x}') = (\mathbf{x}^T\mathbf{x}' + c)^z$.

In parole semplici: elevare al quadrato un prodotto scalare equivale, senza che si veda, a lavorare nello spazio di tutti i prodotti a coppie delle variabili. Aggiungendo una costante prima di elevare a potenza si arricchisce lo spazio con i termini di grado più basso. Un intero feature space polinomiale al prezzo di un prodotto scalare e una potenza.

5.2 Le regole di combinazione#

La via maestra per costruire kernel è partire da kernel noti e combinarli con operazioni “legali”, cioè che preservano la validità. Dati due kernel validi $k_1(\mathbf{x}, \mathbf{x}')$ e $k_2(\mathbf{x}, \mathbf{x}')$, sono kernel validi anche:

1. $k(\mathbf{x}, \mathbf{x}') = c\, k_1(\mathbf{x}, \mathbf{x}')$, con $c > 0$ costante;
2. $k(\mathbf{x}, \mathbf{x}') = f(\mathbf{x})\, k_1(\mathbf{x}, \mathbf{x}')\, f(\mathbf{x}')$, con $f(\cdot)$ funzione qualsiasi;
3. $k(\mathbf{x}, \mathbf{x}') = q\big(k_1(\mathbf{x}, \mathbf{x}')\big)$, con $q(\cdot)$ polinomio a coefficienti non negativi;
4. $k(\mathbf{x}, \mathbf{x}') = \exp\big(k_1(\mathbf{x}, \mathbf{x}')\big)$;
5. $k(\mathbf{x}, \mathbf{x}') = k_1(\mathbf{x}, \mathbf{x}') + k_2(\mathbf{x}, \mathbf{x}')$ (somma di kernel);
6. $k(\mathbf{x}, \mathbf{x}') = k_1(\mathbf{x}, \mathbf{x}')\, k_2(\mathbf{x}, \mathbf{x}')$ (prodotto di kernel);
7. $k(\mathbf{x}, \mathbf{x}') = k_3\big(\boldsymbol{\phi}(\mathbf{x}), \boldsymbol{\phi}(\mathbf{x}')\big)$, dove $\boldsymbol{\phi}(\mathbf{x})$ mappa $\mathbf{x}$ in $\mathbb{R}^M$ e $k_3(\cdot,\cdot)$ è un kernel valido su $\mathbb{R}^M$ (trasformazione degli input);
8. $k(\mathbf{x}, \mathbf{x}') = \mathbf{x}^T \mathbf{A}\, \mathbf{x}'$, con $\mathbf{A}$ matrice simmetrica semidefinita positiva;
9. $k(\mathbf{x}, \mathbf{x}') = k_a(\mathbf{x}_a, \mathbf{x}_a') + k_b(\mathbf{x}_b, \mathbf{x}_b')$;
10. $k(\mathbf{x}, \mathbf{x}') = k_a(\mathbf{x}_a, \mathbf{x}_a')\, k_b(\mathbf{x}_b, \mathbf{x}_b')$;

dove nelle regole 9 e 10 le variabili sono divise in due sottoinsiemi, non necessariamente disgiunti, $\mathbf{x} = \{\mathbf{x}_a\} \cup \{\mathbf{x}_b\}$, e $k_a$, $k_b$ sono kernel validi sui rispettivi sottospazi.

Il modo d’uso è sempre lo stesso: si parte da kernel elementari di cui la validità è nota (il kernel lineare $\mathbf{x}^T\mathbf{x}'$ su tutti), si applica una catena di regole, e si è garantiti che il risultato sia un kernel. Attenzione a due dettagli ricorrenti negli errori d’esame: nella regola 1 la costante deve essere positiva, e nella regola 3 il polinomio deve avere tutti i coefficienti non negativi (un termine con segno meno rompe la garanzia).

In parole semplici: i kernel si combinano come mattoncini: sommarli, moltiplicarli, esponenziarli, riscalarli con costanti positive produce sempre altri kernel. La tabella delle regole è la “grammatica” delle combinazioni lecite: se una funzione si riesce a smontare in kernel elementari collegati da queste operazioni, è valida senza bisogno di altri conti.

5.3 Il kernel gaussiano#

Il kernel di gran lunga più usato in pratica è il kernel gaussiano (o RBF):

$$k(\mathbf{x}, \mathbf{x}') = \exp\!\left( -\frac{\lVert \mathbf{x} - \mathbf{x}' \rVert^2}{2\sigma^2} \right)$$

La sua validità si dimostra con le regole della sezione precedente, espandendo il quadrato della norma:

$$\lVert \mathbf{x} - \mathbf{x}' \rVert^2 = \mathbf{x}^T\mathbf{x} - 2\, \mathbf{x}^T\mathbf{x}' + \mathbf{x}'^T\mathbf{x}'$$

da cui il kernel si fattorizza in

$$k(\mathbf{x}, \mathbf{x}') = \exp\!\left( -\frac{\mathbf{x}^T\mathbf{x}}{2\sigma^2} \right) \exp\!\left( \frac{\mathbf{x}^T\mathbf{x}'}{\sigma^2} \right) \exp\!\left( -\frac{\mathbf{x}'^T\mathbf{x}'}{2\sigma^2} \right)$$

Il fattore centrale è l’esponenziale del kernel lineare riscalato con costante positiva $1/\sigma^2$: valido per le regole 1 e 4. I due fattori esterni hanno la forma $f(\mathbf{x}) \cdot (\dots) \cdot f(\mathbf{x}')$ con $f(\mathbf{x}) = \exp(-\lVert\mathbf{x}\rVert^2 / 2\sigma^2)$: regola 2. Il kernel gaussiano è dunque valido.

Il feature space corrispondente al kernel gaussiano ha dimensione infinita: sviluppando in serie di Taylor l’esponenziale del prodotto scalare compaiono i termini polinomiali di tutti i gradi, cioè il kernel gaussiano equivale a un prodotto scalare su un vettore infinito di feature polinomiali. È l’esempio perfetto della potenza del kernel trick: nessun metodo esplicito potrebbe mai lavorare in quello spazio.

Il kernel gaussiano si può inoltre estendere sostituendo il prodotto scalare $\mathbf{x}^T\mathbf{x}'$ con un kernel non lineare valido $\kappa(\mathbf{x}, \mathbf{x}')$:

$$k(\mathbf{x}, \mathbf{x}') = \exp\!\left( -\frac{\kappa(\mathbf{x}, \mathbf{x}) - 2\,\kappa(\mathbf{x}, \mathbf{x}') + \kappa(\mathbf{x}', \mathbf{x}')}{2\sigma^2} \right)$$

che resta un kernel valido e permette di misurare la distanza in un feature space non lineare a scelta.

Come similarità, il kernel gaussiano è molto leggibile: vale il massimo quando $\mathbf{x} = \mathbf{x}'$ e decresce verso zero al crescere della distanza euclidea; due punti sono “simili” se e solo se sono vicini nello spazio di input, con una scala di vicinanza governata da $\sigma$.

In parole semplici: il kernel gaussiano dice che due punti si somigliano quanto più sono vicini, con un raggio di somiglianza regolabile. Dietro questa formula innocua c’è uno spazio di feature a infinite dimensioni: usarlo con il kernel trick significa far girare un modello lineare in uno spazio che non potrebbe fisicamente esistere in memoria.

5.4 Kernel su input non vettoriali e da modelli generativi#

I metodi kernel si estendono anche a input diversi dai vettori reali: grafi, insiemi, stringhe, testi. Il motivo è strutturale: poiché il kernel rappresenta soltanto una misura di similarità tra due campioni, basta saper definire una similarità valida tra oggetti di quel tipo, senza bisogno che gli oggetti abbiano coordinate.

Un esempio classico per gli insiemi: dati due insiemi $A_1$ e $A_2$,

$$k(A_1, A_2) = 2^{\lvert A_1 \cap A_2 \rvert}$$

dove $\lvert \cdot \rvert$ denota la cardinalità. È un kernel valido: corrisponde al prodotto scalare nel feature space indicizzato da tutti i possibili sottoinsiemi $U$, con $\phi_U(A) = 1$ se $U \subseteq A$ e $0$ altrimenti; il prodotto scalare conta i sottoinsiemi contenuti in entrambi, che sono esattamente $2^{\lvert A_1 \cap A_2 \rvert}$.

È possibile anche definire kernel a partire da modelli generativi probabilistici. Dato un modello generativo $p(\mathbf{x})$, si definisce

$$k(\mathbf{x}, \mathbf{x}') = p(\mathbf{x})\, p(\mathbf{x}')$$

È un kernel valido, perché corrisponde al prodotto scalare nel feature space unidimensionale definito dalla mappa $\mathbf{x} \to p(\mathbf{x})$. L’interpretazione: due input sono simili se entrambi hanno alta probabilità sotto il modello generativo.

In parole semplici: per usare i metodi kernel su frasi, molecole o insiemi non serve inventare coordinate numeriche per quegli oggetti: basta una funzione che dica quanto due oggetti si somigliano e che superi il test di validità. È molto più naturale dire “queste due frasi si somigliano tanto” che rappresentare una frase come un vettore.

6. Regressione kernel: Nadaraya-Watson#

Prima dei processi gaussiani conviene vedere l’uso più diretto possibile dei kernel in regressione: metodi memory-based puri, in cui la predizione è una media dei target dei punti vicini.

6.1 Regressione k-NN#

Il k-nearest neighbour si applica alla regressione predicendo, per un nuovo punto $\mathbf{x}$, la media dei target dei $k$ campioni più vicini nel training set:

$$y(\mathbf{x}) = \frac{1}{k} \sum_{\mathbf{x}_n \in N_k(\mathbf{x}, \mathcal{D})} t_n$$

dove $N_k(\mathbf{x}, \mathcal{D})$ è l’insieme dei $k$ punti di $\mathcal{D}$ più vicini a $\mathbf{x}$. Il difetto è visibile appena si traccia la funzione appresa: l’output è molto rumoroso e discontinuo, perché spostando $\mathbf{x}$ il vicinato cambia a scatti (un punto entra, un altro esce) e la media salta di conseguenza.

6.2 Il modello di Nadaraya-Watson#

Il modello di Nadaraya-Watson, detto anche kernel regression, elimina le discontinuità sostituendo il vicinato rigido con una media pesata di tutti i campioni, dove i pesi sono dati da una funzione kernel:

Ogni campione contribuisce alla predizione in proporzione alla sua similarità con $\mathbf{x}$: i punti vicini dominano, i punti lontani contano poco o nulla, e la transizione è graduale, quindi la funzione appresa è liscia se il kernel lo è. Il modello si può anche derivare in modo principiato partendo da una stima kernel della densità congiunta di input e target (Bishop, sezione 2.5.1). Le scelte tipiche del kernel sono:

• kernel di Epanechnikov, a supporto limitato: solo i punti entro una finestra attorno a $\mathbf{x}$ ricevono peso non nullo;
• kernel gaussiano, a supporto infinito: tutti i punti ricevono un peso, che decade esponenzialmente con la distanza.

In parole semplici: il k-NN fa votare solo i $k$ vicini, tutti con lo stesso peso, e il risultato è una funzione a scalini. Nadaraya-Watson fa votare tutti, ma con peso proporzionale alla vicinanza: il risultato è la stessa idea, “chiedi ai vicini”, con una risposta finalmente liscia.

7. Processi gaussiani per la regressione#

I processi gaussiani (Gaussian Processes, GP) sono il punto d’incontro tra due fili del corso: l’approccio bayesiano alla regressione (capitolo 3) e i kernel. Come ogni metodo bayesiano, forniscono non solo una predizione per il target ma anche una valutazione dell’incertezza su quella predizione; come ogni metodo kernel, lavorano con le similarità tra punti e non richiedono un feature space esplicito.

7.1 La regressione bayesiana rivisitata: dal prior sui pesi al prior sulle funzioni#

Si parte dalle stesse assunzioni della regressione lineare bayesiana: modello $y(\mathbf{x}) = \mathbf{w}^T\boldsymbol{\phi}(\mathbf{x})$ e prior gaussiano sui pesi

$$p(\mathbf{w}) = \mathcal{N}(\mathbf{w} \mid \mathbf{0},\, \tau^2 \mathbf{I})$$

L’osservazione chiave è chiedersi che distribuzione induca questo prior sugli output della funzione di regressione valutata nei punti di training. Si consideri il vettore $\mathbf{y} = \boldsymbol{\Phi}\mathbf{w}$ delle $N$ valutazioni $y(\mathbf{x}_1), \dots, y(\mathbf{x}_N)$: è una trasformazione lineare di un vettore gaussiano, quindi è a sua volta gaussiano, con

$$\mathbb{E}[\mathbf{y}] = \boldsymbol{\Phi}\, \mathbb{E}[\mathbf{w}] = \mathbf{0}, \qquad \text{Cov}[\mathbf{y}] = \boldsymbol{\Phi}\, \mathbb{E}[\mathbf{w}\mathbf{w}^T]\, \boldsymbol{\Phi}^T = \tau^2\, \boldsymbol{\Phi}\boldsymbol{\Phi}^T = \mathbf{K}$$

dove $\mathbf{K}$ è la matrice di Gram associata al kernel $k(\mathbf{x}, \mathbf{x}') = \tau^2\, \boldsymbol{\phi}(\mathbf{x})^T\boldsymbol{\phi}(\mathbf{x}')$. Il prior sui pesi si è trasformato in un prior direttamente sui valori della funzione, e la struttura di covarianza di questo prior è interamente descritta dal kernel. Questo suggerisce di saltare del tutto il passaggio per i pesi: si può definire il prior direttamente nello spazio delle funzioni, scegliendo un kernel.

7.2 Definizione di processo gaussiano#

Una distribuzione su un oggetto infinito-dimensionale come una funzione sembra intrattabile; la definizione la rende maneggevole caratterizzandola tramite tutte le sue “fotografie finite”: comunque si scelgano $N$ punti, la distribuzione congiunta dei valori della funzione in quei punti è una gaussiana. Nel caso usato per la regressione, il processo è specificato da due proprietà:

• media nulla: $\mathbb{E}[y(\mathbf{x}_i)] = 0$ per ogni punto (in assenza di conoscenza a priori non c’è motivo di aspettarsi valori positivi piuttosto che negativi);
• covarianza data dal kernel: $\text{Cov}\big(y(\mathbf{x}_i), y(\mathbf{x}_j)\big) = \mathbb{E}\big[y(\mathbf{x}_i)\, y(\mathbf{x}_j)\big] = k(\mathbf{x}_i, \mathbf{x}_j)$.

Dato il kernel, il processo gaussiano è completamente caratterizzato. Questo fornisce anche un’interpretazione probabilistica della funzione kernel: il kernel è la covarianza tra i valori della funzione in due punti.

L’intuizione dietro la scelta è importante. Se si pensa al kernel come a una similarità, un valore alto di $k(\mathbf{x}_i, \mathbf{x}_j)$ per punti simili significa covarianza alta tra $y(\mathbf{x}_i)$ e $y(\mathbf{x}_j)$; poiché la media è zero, covarianza alta significa correlazione alta, cioè: la funzione tende ad assumere valori simili in punti simili. Il prior gaussiano di processo è quindi un modo di imporre una forma di regolarità sulle funzioni: si dà probabilità alta alle funzioni lisce rispetto al kernel scelto. Attenzione a un fraintendimento comune: la covarianza riguarda la distribuzione della funzione, non dei dati; si sta dicendo che è molto probabile che la funzione di regressione assegni target simili a input simili.

In parole semplici: un processo gaussiano è un modo di dire “non so che funzione sia, ma scommetto che sia liscia” in linguaggio probabilistico. Invece di mettere un prior sui pesi di un modello, si mette un prior direttamente sulle funzioni: il kernel decide quali funzioni sono plausibili (quelle che variano poco tra punti simili) e quali no.

7.3 Il modello di osservazione e la distribuzione dei target#

Per usare il GP in regressione si adotta la solita assunzione: i target osservati sono i valori di una funzione ignota più rumore gaussiano additivo,

$$t_n = y(\mathbf{x}_n) + \varepsilon_n, \qquad \varepsilon_n \sim \mathcal{N}(0, \sigma^2)$$

con rumore indipendente tra campioni diversi. Raccogliendo i valori della funzione nel vettore $\mathbf{y}$ e i target nel vettore $\mathbf{t}$, la distribuzione condizionata dei target dati i valori della funzione è una gaussiana isotropa con covarianza diagonale:

$$p(\mathbf{t} \mid \mathbf{y}) = \mathcal{N}(\mathbf{t} \mid \mathbf{y},\, \sigma^2 \mathbf{I}_N)$$

mentre il prior sui valori della funzione, per definizione di GP, è

$$p(\mathbf{y}) = \mathcal{N}(\mathbf{y} \mid \mathbf{0},\, \mathbf{K})$$

con $\mathbf{K}$ la matrice di Gram del kernel scelto. Integrando su $\mathbf{y}$ (tutto è gaussiano, quindi anche il risultato lo è) si ottiene la distribuzione marginale dei target:

$$p(\mathbf{t}) = \int p(\mathbf{t} \mid \mathbf{y})\, p(\mathbf{y})\, d\mathbf{y} = \mathcal{N}(\mathbf{t} \mid \mathbf{0},\, \mathbf{C}_N), \qquad \mathbf{C}_N = \mathbf{K} + \sigma^2 \mathbf{I}_N$$

La covarianza $\mathbf{C}_N$ somma i due contributi di aleatorietà, che sono indipendenti: la variabilità della funzione (tramite $\mathbf{K}$) e il rumore di osservazione (tramite $\sigma^2 \mathbf{I}_N$); elemento per elemento, $C_N(\mathbf{x}_n, \mathbf{x}_m) = k(\mathbf{x}_n, \mathbf{x}_m) + \sigma^2\, \delta_{nm}$. Questa matrice è l’oggetto centrale per la predizione.

7.4 La distribuzione predittiva#

Si supponga di aver osservato $N$ punti e di ricevere un nuovo input $\mathbf{x}_{N+1}$, per il quale si vuole predire il target $t_{N+1}$. Il vettore esteso $\mathbf{t}_{N+1} = (t_1, \dots, t_N, t_{N+1})^T$ ha, per le stesse ragioni di prima, distribuzione gaussiana a media nulla con covarianza $\mathbf{C}_{N+1}$, che si costruisce incrementalmente da $\mathbf{C}_N$ aggiungendo una riga e una colonna:

$$\mathbf{C}_{N+1} = \begin{pmatrix} \mathbf{C}_N & \mathbf{k} \\ \mathbf{k}^T & c \end{pmatrix}$$

dove:

• $\mathbf{k}$ è il vettore delle valutazioni del kernel tra tutti i punti osservati e il nuovo punto, $\mathbf{k} = \big( k(\mathbf{x}_1, \mathbf{x}_{N+1}), \dots, k(\mathbf{x}_N, \mathbf{x}_{N+1}) \big)^T$;
• $c = k(\mathbf{x}_{N+1}, \mathbf{x}_{N+1}) + \sigma^2$ è l’elemento diagonale relativo al nuovo punto.

La distribuzione predittiva è la distribuzione del nuovo target condizionata a tutti i dati raccolti, $p(t_{N+1} \mid \mathbf{t}_N)$. Il condizionamento di una gaussiana congiunta è ancora una gaussiana, con espressioni in forma chiusa per media e varianza:

7.5 Interpretazione della media e della varianza predittive#

La media. La predizione $m(\mathbf{x}_{N+1}) = \mathbf{k}^T \mathbf{C}_N^{-1} \mathbf{t}_N$ è una combinazione lineare pesata dei target osservati. Il vettore $\mathbf{k}$ dice quanto il nuovo punto è simile a ciascuno dei punti precedenti: intuitivamente, se il nuovo punto è molto simile a un punto già visto, si vuole dare un peso alto al target di quel punto, ed è esattamente ciò che la formula fa. La matrice $\mathbf{C}_N^{-1}$ aggiusta questi pesi tenendo conto della struttura di similarità interna ai dati di training (quanto i vecchi punti si somigliano tra loro, tramite $\mathbf{K}$) e del rumore irriducibile (tramite $\sigma^2\mathbf{I}$): serve a garantire la scala corretta della predizione e a non contare più volte l’informazione portata da punti di training ridondanti. Se per un momento si immagina $\mathbf{C}_N \approx \mathbf{I}$, la formula si riduce a “somma dei target pesati con la similarità”, che è l’essenza del meccanismo.

La varianza. La formula $\sigma^2(\mathbf{x}_{N+1}) = c - \mathbf{k}^T \mathbf{C}_N^{-1} \mathbf{k}$ si legge come “incertezza a priori meno informazione guadagnata”:

• $c = \sigma^2 + k(\mathbf{x}_{N+1}, \mathbf{x}_{N+1})$ è la varianza che il punto avrebbe senza osservazioni: rumore irriducibile più variabilità a priori della funzione nel punto;
• $\mathbf{k}^T \mathbf{C}_N^{-1} \mathbf{k}$ è una quantità sicuramente non negativa (perché $\mathbf{C}_N$ è definita positiva) che viene sottratta, ed è grande quando il nuovo punto è simile ai punti osservati: in quel caso il vettore $\mathbf{k}$ ha componenti grandi, mentre $\mathbf{C}_N$ non dipende dal nuovo punto.

Il comportamento risultante è esattamente quello che ci si aspetta da un metodo bayesiano sensato: se il nuovo punto cade vicino a punti già osservati, il processo ha molta informazione e la varianza predittiva è piccola; se cade lontano da tutti i dati, il termine sottratto è quasi nullo e la varianza resta vicina a quella a priori, cioè grande.

In parole semplici: il GP predice facendo una media intelligente dei target dei punti che somigliano al punto nuovo, e insieme alla predizione dichiara quanto è sicuro: molto sicuro dove ha visto tanti dati, poco sicuro dove sta estrapolando. La barra d’errore non è un accessorio: esce dalle stesse formule della predizione.

Visivamente, in un problema di regressione 1D risolto con un GP (kernel gaussiano con ampiezza $K = 3$, length scale $\ell = 0.8$ e rumore $\sigma^2 = 0.2$), si traccia la curva della media predittiva $m(x)$ al variare di $x$ e, attorno a essa, la banda di confidenza al 95% ottenuta come $m(x) \pm 1.96\, \sigma(x)$. Nelle regioni ricche di punti di training la banda è stretta; nelle regioni prive di punti la banda si allarga, in accordo con l’analisi della formula della varianza.

7.6 Scelta del kernel e degli iperparametri#

Il kernel del GP si progetta con gli approcci usuali della sezione 5. Due famiglie tipicamente usate con i GP sono:

• il kernel gaussiano, nella forma con ampiezza e length scale espliciti:

$$k(\mathbf{x}_i, \mathbf{x}_j) = K \exp\!\left( -\frac{\lVert \mathbf{x}_i - \mathbf{x}_j \rVert^2}{2\,\ell^2} \right)$$

• il kernel esponenziale, $k(\mathbf{x}_i, \mathbf{x}_j) = \exp\!\left( -\theta\, \lVert \mathbf{x}_i - \mathbf{x}_j \rVert \right)$, che decade con la distanza (non con il suo quadrato) e genera funzioni meno lisce.

Nel kernel gaussiano, $K > 0$ è una costante di ampiezza e $\ell$ è la length scale, che gioca il ruolo della deviazione standard della campana: due punti sono considerati simili se la loro distanza è piccola rispetto a $\ell$. Da non confondere: il kernel gaussiano non ha nulla a che vedere con i processi gaussiani in quanto tali; condividono solo l’uso della funzione gaussiana, e un GP può benissimo usare un kernel non gaussiano.

Come si scelgono i valori degli iperparametri $K$, $\ell$ e $\sigma^2$? Due strade:

1. conoscenza di dominio: se si sa qualcosa del problema (per esempio l’entità del rumore di misura), si possono fissare direttamente;
2. massima verosimiglianza: si usano i dati per stimare gli iperparametri massimizzando la verosimiglianza marginale $p(\mathbf{t})$, cioè la probabilità che i campioni siano generati da una gaussiana con la struttura di covarianza indotta dal kernel. È l’approccio implementato di default in molte librerie (in Python, GaussianProcessRegressor di scikit-learn).

L’iperparametro più importante per il comportamento del modello è la length scale, che agisce come manopola di regolarizzazione:

• aumentando $\ell$ (per esempio da 0.8 a 8) l’argomento dell’esponenziale si riduce in valore assoluto e i valori del kernel crescono: il modello considera “simili” anche punti lontani. La funzione appresa diventa più liscia, l’incertezza complessiva più piccola e quasi uniforme, con poca differenza tra regioni dense e regioni vuote. È una regolarizzazione forte: bias alto, varianza bassa (nel senso del compromesso bias-varianza);
• diminuendo $\ell$ (per esempio da 0.8 a 0.08) la similarità decade molto in fretta: la media predittiva diventa meno regolare e la differenza di incertezza tra regioni dense e vuote si accentua molto. Regolarizzazione debole: bias basso, varianza alta.

Il rumore $\sigma^2$ ha un effetto diverso: non incide molto sulla levigatezza della funzione, ma incide in modo significativo sull’ampiezza dell’incertezza predittiva. Con $\sigma^2$ grande (per esempio 10) la banda di confidenza si allarga ovunque; con $\sigma^2$ piccolo si restringe. Per il kernel gaussiano, comunque, l’iperparametro che governa la regolarità della soluzione è la length scale.

In parole semplici: $\ell$ decide fino a che distanza due punti “si parlano”. Con $\ell$ grande tutti parlano con tutti e la curva viene piatta e tranquilla; con $\ell$ piccolo ognuno ascolta solo i vicinissimi e la curva insegue ogni punto, con grande incertezza appena fuori dai dati. È la stessa storia del compromesso bias-varianza, raccontata da un solo numero.

7.7 GP e regressione bayesiana a confronto; natura non parametrica#

Il confronto con la regressione lineare bayesiana chiude il cerchio:

• la regressione bayesiana con $M$ funzioni base e prior gaussiano sui pesi è un processo gaussiano, quello con kernel $k(\mathbf{x}, \mathbf{x}') = \tau^2 \boldsymbol{\phi}(\mathbf{x})^T\boldsymbol{\phi}(\mathbf{x}')$; il GP è la generalizzazione che permette kernel qualunque, inclusi quelli con feature space infinito (come il gaussiano), irraggiungibili per qualsiasi modello a basi esplicite;
• il costo computazionale si ribalta come nel caso della ridge: la regressione bayesiana lavora con matrici $M \times M$, il GP deve invertire $\mathbf{C}_N$, che è $N \times N$; il GP conviene quando $M$ è enorme o infinito, diventa oneroso quando $N$ è molto grande;
• il GP è un metodo non parametrico: non c’è alcun vettore di parametri da stimare, i dati vengono usati direttamente per produrre le predizioni. Le uniche quantità da fissare sono gli iperparametri del kernel e il rumore, tipicamente stimati per massima verosimiglianza.

Un’ultima nota di prospettiva: i GP nascono per la regressione, ma si possono estendere alla classificazione binaria applicando una funzione sigmoidale alla media predittiva $m(\mathbf{x})$, ottenendo un valore in $(0,1)$ interpretabile come probabilità della classe positiva; l’addestramento in quel caso richiede tecniche approssimate che escono dallo scopo del corso.

In parole semplici: la regressione bayesiana e il GP sono la stessa fotografia scattata da due lati: una ragiona sui pesi, l’altro direttamente sulle funzioni. Il GP però può usare similarità che nessun insieme finito di basi può replicare, e paga questo lusso con conti che crescono con il cubo del numero di dati.

8. Esercizi d’esame svolti#

8.1 Verificare la validità di un kernel#

Traccia. Siano $\mathbf{x}, \mathbf{y} \in \mathbb{R}^d$ e sia $\mathbf{1}$ il vettore di tutti uno di dimensione opportuna. Dire se le seguenti funzioni sono kernel validi, motivando le risposte:

1. $k_1(\mathbf{x}, \mathbf{y}) = \mathbf{x}^T\mathbf{y} + \mathbf{x}^T\mathbf{1} + \mathbf{y}^T\mathbf{1} + d$
2. $k_2(\mathbf{x}, \mathbf{y}) = \mathbf{x}^T\mathbf{y} - \lVert \mathbf{x} \rVert^2$
3. $k_3(\mathbf{x}, \mathbf{y}) = \big( k_1(\cos(\mathbf{x}), \cos(\mathbf{y})) \big)^3$, con il coseno applicato elemento per elemento
4. $k_4(\mathbf{x}, \mathbf{y}) = \exp\big( k_2(\mathbf{x}, \mathbf{y}) + k_2(\mathbf{y}, \mathbf{x}) \big)$

Svolgimento del punto 1. Un primo istinto è consultare la tabella delle regole di combinazione: il termine $\mathbf{x}^T\mathbf{y}$ è il kernel lineare, ma i termini $\mathbf{x}^T\mathbf{1}$ e $\mathbf{y}^T\mathbf{1}$ presi singolarmente non sono kernel (non sono nemmeno funzioni simmetriche di entrambe le variabili), quindi la tabella da sola non chiude il problema. Un secondo istinto è cercare un controesempio valutando la funzione su coppie specifiche di punti: ma da valutazioni puntuali che non evidenziano violazioni (di simmetria o di semidefinitezza) non si può concludere nulla; servono solo a scartare, non a promuovere.

La strada giusta è tentare di esibire un feature mapping, cioè di fattorizzare la funzione come prodotto scalare. Ricordando che $\mathbf{1}^T\mathbf{1} = d$, si riconosce l’espansione di

$$(\mathbf{x} + \mathbf{1})^T (\mathbf{y} + \mathbf{1}) = \mathbf{x}^T\mathbf{y} + \mathbf{x}^T\mathbf{1} + \mathbf{1}^T\mathbf{y} + \mathbf{1}^T\mathbf{1} = \mathbf{x}^T\mathbf{y} + \mathbf{x}^T\mathbf{1} + \mathbf{y}^T\mathbf{1} + d = k_1(\mathbf{x}, \mathbf{y})$$

La funzione è dunque il prodotto scalare $\boldsymbol{\phi}(\mathbf{x})^T\boldsymbol{\phi}(\mathbf{y})$ nel feature space definito da $\boldsymbol{\phi}(\mathbf{x}) = \mathbf{x} + \mathbf{1}$: è un kernel valido. In alternativa si può invocare la regola 7: $k_1$ è il kernel lineare applicato agli input trasformati $\mathbf{x} \to \mathbf{x} + \mathbf{1}$.

Svolgimento del punto 2. Si controlla subito la simmetria:

$$k_2(\mathbf{x}, \mathbf{y}) = \mathbf{x}^T\mathbf{y} - \lVert \mathbf{x} \rVert^2, \qquad k_2(\mathbf{y}, \mathbf{x}) = \mathbf{x}^T\mathbf{y} - \lVert \mathbf{y} \rVert^2$$

Le due espressioni differiscono non appena $\lVert \mathbf{x} \rVert \neq \lVert \mathbf{y} \rVert$: la funzione non è simmetrica, quindi non è un kernel valido. Quando la simmetria manca, questa singola osservazione è una motivazione sufficiente e completa.

Svolgimento del punto 3. Si procede in due passi con le regole di combinazione:

1. la trasformazione $\boldsymbol{\phi}(\mathbf{x}) = \cos(\mathbf{x})$ (coseno elemento per elemento) mappa $\mathbb{R}^d$ in $\mathbb{R}^d$; poiché $k_1$ è un kernel valido su $\mathbb{R}^d$ (punto 1), per la regola 7 anche $k_1(\cos(\mathbf{x}), \cos(\mathbf{y}))$ è un kernel valido;
2. l’elevamento al cubo si gestisce con la regola 3, prendendo il polinomio $q(z) = z^3$ che ha coefficienti non negativi; equivalentemente, si può applicare due volte la regola 6 (prodotto di kernel): $k \cdot k$ è un kernel, e $(k \cdot k) \cdot k$ pure.

Quindi $k_3$ è un kernel valido.

Svolgimento del punto 4. La tentazione è forte: “somma di kernel (regola 5) dentro un esponenziale (regola 4), quindi valido”. Ma il ragionamento è sbagliato in partenza: le regole si applicano solo partendo da kernel validi, e $k_2$ non lo è (punto 2). Dal fallimento delle regole, però, non si può concludere che $k_4$ non sia valido: le regole danno condizioni sufficienti, non necessarie. Bisogna fare il calcolo esplicito dell’argomento dell’esponenziale:

$$k_2(\mathbf{x}, \mathbf{y}) + k_2(\mathbf{y}, \mathbf{x}) = \mathbf{x}^T\mathbf{y} - \lVert \mathbf{x} \rVert^2 + \mathbf{y}^T\mathbf{x} - \lVert \mathbf{y} \rVert^2 = -\big( \lVert \mathbf{x} \rVert^2 + \lVert \mathbf{y} \rVert^2 - 2\, \mathbf{x}^T\mathbf{y} \big) = -\lVert \mathbf{x} - \mathbf{y} \rVert^2$$

avendo riconosciuto l’espansione del quadrato della norma della differenza (il prodotto scalare è simmetrico, quindi $\mathbf{x}^T\mathbf{y} + \mathbf{y}^T\mathbf{x} = 2\,\mathbf{x}^T\mathbf{y}$). Dunque

$$k_4(\mathbf{x}, \mathbf{y}) = \exp\big( -\lVert \mathbf{x} - \mathbf{y} \rVert^2 \big)$$

che è esattamente il kernel gaussiano (con $2\sigma^2 = 1$), la cui validità è stata dimostrata nella sezione 5.3: $k_4$ è un kernel valido. La morale, preziosa per l’esame: è possibile costruire un kernel valido combinando funzioni che kernel non sono; in questi casi la tabella delle regole non basta e serve la verifica diretta.

8.2 Vero o falso sui processi gaussiani#

Traccia. Dire se le seguenti affermazioni sui processi gaussiani sono vere o false, motivando le risposte.

1. Più campioni abbiamo in una zona dello spazio di input attorno a un punto $\mathbf{x}$, più è probabile che la varianza del processo diminuisca in $\mathbf{x}$.
2. Possiamo scegliere qualunque tipo di distribuzione a priori per un GP.
3. I processi gaussiani possono essere usati solo per la regressione.
4. Lontano dalle regioni in cui abbiamo punti, la varianza del GP diventa sempre più grande.
5. Come nei modelli lineari, la varianza considerata dipende dal punto $\mathbf{x}$ dello spazio di input.

Punto 1: vera. Dove ci sono molti punti osservati, la predizione del GP dispone di molta informazione localizzata e la sua varianza è piccola. La giustificazione intuitiva è sufficiente all’esame, ma si può anche argomentare analiticamente: la varianza predittiva in $\mathbf{x}$ è

$$\sigma^2(\mathbf{x}) = \sigma^2 + k(\mathbf{x}, \mathbf{x}) - \mathbf{k}^T \mathbf{C}_N^{-1}\, \mathbf{k}$$

con $\mathbf{k} = \big(k(\mathbf{x}_1, \mathbf{x}), \dots, k(\mathbf{x}_N, \mathbf{x})\big)^T$. Più punti di training sono vicini (cioè simili) a $\mathbf{x}$, più le componenti di $\mathbf{k}$ sono grandi, più grande è la quantità sottratta, più piccola è la varianza.

Punto 2: falsa. In un processo gaussiano la distribuzione a priori sui valori della funzione, $p(\mathbf{y})$, non è libera: è forzata a essere una gaussiana con media nulla e matrice di covarianza pari alla matrice di Gram $\mathbf{K}$ indotta dal kernel. La libertà di modellazione sta nella scelta del kernel, non nella forma della distribuzione.

Punto 3: vera (ai fini del corso). L’output del GP è la media predittiva $m(\mathbf{x})$, un numero reale, quindi il metodo così com’è risolve problemi di regressione. Come informazione aggiuntiva: i GP si possono adattare alla classificazione binaria applicando una sigmoide a $m(\mathbf{x})$ e interpretando il risultato come probabilità della classe positiva, ma l’addestramento in quel contesto richiede tecniche fuori dallo scopo del corso.

Punto 4: vera, per la stessa ragione, ribaltata, del punto 1: lontano dai dati le componenti del vettore $\mathbf{k}$ sono piccole (il nuovo punto non somiglia a nessun punto osservato), la quantità sottratta $\mathbf{k}^T\mathbf{C}_N^{-1}\mathbf{k}$ tende a zero e la varianza predittiva tende al suo valore a priori $\sigma^2 + k(\mathbf{x}, \mathbf{x})$, il massimo possibile.

Punto 5: falsa, sotto entrambe le letture possibili dell’affermazione:

• se per “varianza” si intende quella del rumore irriducibile $\sigma^2$: in entrambi i modelli (lineare e GP) il rumore è assunto omoschedastico, cioè con varianza costante che non dipende dall’input; l’affermazione di dipendenza da $\mathbf{x}$ è falsa in tutti e due i casi;
• se per “varianza” si intende quella della predizione: nel GP esiste ed effettivamente dipende da $\mathbf{x}$, ma nei modelli lineari (non bayesiani) una varianza di predizione non viene proprio fornita: il modello restituisce solo la stima puntuale. Il parallelo “come nei modelli lineari” è quindi comunque falso.

Glossario#

Termine	Definizione
Feature mapping	Trasformazione $\boldsymbol{\phi}$ che porta gli input in uno spazio a dimensionalità più alta dove i pattern diventano lineari.
Metodo parametrico	Metodo la cui soluzione dipende da un numero fisso di parametri stimati dai dati; dopo l’addestramento il training set può essere scartato.
Metodo memory-based (non parametrico)	Metodo che memorizza il training set e lo usa direttamente al momento della predizione; addestramento veloce, predizione costosa.
Funzione kernel	Prodotto scalare tra i vettori di feature di due campioni, $k(\mathbf{x}, \mathbf{x}') = \boldsymbol{\phi}(\mathbf{x})^T\boldsymbol{\phi}(\mathbf{x}')$; si interpreta come misura di similarità.
Kernel stazionario	Kernel che dipende solo dalla differenza degli argomenti, $k(\mathbf{x} - \mathbf{x}')$.
Kernel omogeneo (RBF)	Kernel che dipende solo dalla distanza tra gli argomenti, $k(\lVert \mathbf{x} - \mathbf{x}' \rVert)$.
Kernel trick	Riscrittura di un algoritmo lineare in modo che gli input compaiano solo dentro prodotti scalari, sostituibili con un kernel: l’algoritmo lavora in un feature space implicito.
Rappresentazione duale	Riformulazione della ridge regression con incognite $\mathbf{a} \in \mathbb{R}^N$ (una per campione) al posto dei pesi $\mathbf{w} \in \mathbb{R}^M$; soluzione $\mathbf{a} = (\mathbf{K} + \lambda\mathbf{I}_N)^{-1}\mathbf{t}$.
Matrice di Gram ($\mathbf{K}$)	Matrice $N \times N$ delle similarità tra coppie di campioni, $K_{nm} = k(\mathbf{x}_n, \mathbf{x}_m)$; simmetrica e semidefinita positiva per kernel validi.
Kernel valido	Funzione che corrisponde a un prodotto scalare in qualche feature space; equivalentemente, che genera matrici di Gram semidefinite positive per ogni dataset.
Teorema di Mercer	Una funzione continua, simmetrica e semidefinita positiva è esprimibile come prodotto scalare in uno spazio a dimensionalità alta, eventualmente infinita.
Regole di combinazione	Operazioni (somma, prodotto, esponenziale, riscalamento positivo, trasformazione degli input…) che applicate a kernel validi producono kernel validi.
Kernel polinomiale	$k(\mathbf{x}, \mathbf{x}') = (\mathbf{x}^T\mathbf{x}' + c)^z$: prodotto scalare nel feature space di tutti i monomi fino al grado $z$.
Kernel gaussiano	$k(\mathbf{x}, \mathbf{x}') = \exp(-\lVert\mathbf{x}-\mathbf{x}'\rVert^2/2\sigma^2)$: kernel valido con feature space a dimensione infinita; la similarità decade con la distanza euclidea.
Length scale ($\ell$)	Iperparametro del kernel gaussiano che fissa la scala di distanza entro cui due punti sono considerati simili; agisce da regolarizzatore (grande $\ell$: bias alto e varianza bassa; piccolo $\ell$: viceversa).
Regressione k-NN	Predizione ottenuta come media dei target dei $k$ campioni più vicini; produce funzioni discontinue e rumorose.
Modello di Nadaraya-Watson	Kernel regression: media dei target pesata con le similarità kernel, $y(\mathbf{x}) = \sum_n k(\mathbf{x},\mathbf{x}_n) t_n / \sum_m k(\mathbf{x},\mathbf{x}_m)$.
Kernel di Epanechnikov	Kernel a supporto limitato usato nella kernel regression: solo i punti entro una finestra ricevono peso non nullo.
Processo gaussiano (GP)	Distribuzione di probabilità su una funzione tale che i valori in ogni insieme finito di punti sono congiuntamente gaussiani; specificato da media (nulla) e covarianza (il kernel).
Interpretazione probabilistica del kernel	Nel GP, $k(\mathbf{x}_i, \mathbf{x}_j) = \mathbb{E}[y(\mathbf{x}_i)\, y(\mathbf{x}_j)]$: il kernel è la covarianza tra i valori della funzione in due punti.
Matrice $\mathbf{C}_N$	Covarianza marginale dei target nel GP: $\mathbf{C}_N = \mathbf{K} + \sigma^2\mathbf{I}_N$, somma di variabilità della funzione e rumore di osservazione.
Media predittiva ($m(\mathbf{x})$)	$\mathbf{k}^T\mathbf{C}_N^{-1}\mathbf{t}$: combinazione lineare dei target osservati pesata dalle similarità con il nuovo punto.
Varianza predittiva ($\sigma^2(\mathbf{x})$)	$c - \mathbf{k}^T\mathbf{C}_N^{-1}\mathbf{k}$: incertezza a priori meno informazione guadagnata; piccola vicino ai dati, grande lontano da essi.
Omoschedasticità	Assunzione che la varianza del rumore $\sigma^2$ sia costante, indipendente dal punto di input; vale sia nei modelli lineari sia nei GP.
Verosimiglianza marginale	Probabilità dei target $p(\mathbf{t}) = \mathcal{N}(\mathbf{0}, \mathbf{C}_N)$, usata per stimare gli iperparametri del kernel e $\sigma^2$ per massima verosimiglianza.

Dispensa Machine Learning · Politecnico di Milano